<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="umsroot.css">
<TITLE>
Definite Clause Grammars &mdash; DCGs
</TITLE>
</HEAD>
<BODY >
<A HREF="umsroot068.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="umsroot066.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc167">12.3</A>&nbsp;&nbsp;Definite Clause Grammars &mdash; DCGs</H2><UL>
<LI><A HREF="umsroot069.html#toc100">Simple DCG example</A>
<LI><A HREF="umsroot069.html#toc101">Mapping to Prolog Clauses</A>
<LI><A HREF="umsroot069.html#toc102">Parsing other Data Structures</A>
</UL>

<A NAME="dcg"></A>
<A NAME="@default681"></A>
<A NAME="@default682"></A>
<A NAME="@default683"></A>
<A NAME="@default684"></A>
Grammar rules are described in many standard Prolog texts ([<A HREF="umsroot159.html#clocksin81"><CITE>2</CITE></A>]).
In ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> they are provided by a predefined global<SUP><A NAME="text18" HREF="umsroot066.html#note18">3</A></SUP> macro for
<TT>-</TT><TT>-&gt;/2</TT>.
When the parser reads a clause whose main functor is <TT>-</TT><TT>-&gt;/2</TT>, it transforms 
it according to the standard rules.
The syntax for DCGs is as follows: 
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
grammar_rule --&gt; grammar_head, ['--&gt;'], grammar_body.

grammar_head --&gt; non_terminal.
grammar_head --&gt; non_terminal, [','], terminal.

grammar_body --&gt; grammar_body, [','], grammar_body.
grammar_body --&gt; grammar_body, [';'], grammar_body.
grammar_body --&gt; grammar_body, ['-&gt;'], grammar_body.
grammar_body --&gt; grammar_body, ['|'], grammar_body.
grammar_body --&gt; iteration_spec, ['do'], grammar_body.
grammar_body --&gt; ['-?-&gt;'], grammar_body.
grammar_body --&gt; grammar_body_item.

grammar_body_item --&gt; ['!'].
grammar_body_item --&gt; ['{'], Prolog_goals, ['}'].
grammar_body_item --&gt; non_terminal.
grammar_body_item --&gt; terminal.
</PRE></BLOCKQUOTE>
The non-terminals are syntactically identical to prolog goals (atom, compound
term or variable), the terminals are lists of prolog terms (typically
characters or tokens). Every 
term is transformed, unless it is enclosed in curly brackets. The control
constructs like conjunction <TT>,/2</TT>, disjunction (<TT>;/2</TT> or <TT>|/2</TT>),
the cut (<TT>!/0</TT>), the condition (<TT>-&gt;/1</TT>) and do-loops do not need to
be enclosed in curly brackets.<BR>
<BR>
The grammar can be accessed with the built-in <A HREF="../bips/kernel/control/phrase-3.html"><B>phrase/3</B></A><A NAME="@default685"></A>.
The first argument of <A HREF="../bips/kernel/control/phrase-3.html"><B>phrase/3</B></A><A NAME="@default686"></A> is the name of the
grammar to be used, the 
second argument one is a list containing the input to be parsed. If the
parsing is successful the built-in will succeed.
For instance with the grammar
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
a --&gt; [] | [z], a.
</PRE></BLOCKQUOTE>
<TT>phrase(a, X, [])</TT> will give on backtracking: <TT>X = [z] ; X = [z, z] ; X = [z, z, z] ; ...</TT>.<BR>
<BR>
<A NAME="toc100"></A>
<H3 CLASS="subsection"><A NAME="htoc168">12.3.1</A>&nbsp;&nbsp;Simple DCG example</H3>
The following example illustrates a simple grammar declared using the DCGs.
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
sentence --&gt; imperative, noun_phrase(Number), verb_phrase(Number).

imperative, [you] --&gt; [].
imperative --&gt; [].

noun_phrase(Number) --&gt; determiner, noun(Number).
noun_phrase(Number) --&gt; pronom(Number).

verb_phrase(Number) --&gt; verb(Number).
verb_phrase(Number) --&gt; verb(Number), noun_phrase(_).

determiner --&gt; [the].

noun(singular) --&gt; [man].
noun(singular) --&gt; [apple].
noun(plural) --&gt; [men].
noun(plural) --&gt; [apples].

verb(singular) --&gt; [eats].
verb(singular) --&gt; [sings].
verb(plural) --&gt; [eat].
verb(plural) --&gt; [sing].

pronom(plural) --&gt; [you].
</PRE></BLOCKQUOTE>
The above grammar may be successfully parsed
using <A HREF="../bips/kernel/control/phrase-3.html"><B>phrase/3</B></A><A NAME="@default687"></A>. If the predicate
succeeds then the input has been parsed successfully.
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
[eclipse 1]: phrase(sentence, [the,man,eats,the,apple], []).

yes.
[eclipse 2]: phrase(sentence, [the,men,eat], []).

yes.
[eclipse 3]: phrase(sentence, [the,men,eats], []).

no.
[eclipse 4]: phrase(sentence, [eat,the,apples], []).

yes.
[eclipse 5]: phrase(sentence, [you,eat,the,man], []). 

yes.
</PRE></BLOCKQUOTE>
The predicate <A HREF="../bips/kernel/control/phrase-3.html"><B>phrase/3</B></A><A NAME="@default688"></A> may be used to return the point at which
parsing of a grammar fails &mdash; if the returned list is empty then the
input has been successfully parsed.
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
[eclipse 1]: phrase(sentence, [the,man,eats,something,nasty],X).

X = [something, nasty]     More? (;) 

no (more) solution.
[eclipse 2]: phrase(sentence, [eat,the,apples],X).

X = [the, apples]     More? (;) 

X = []     More? (;) 

no (more) solution.
[eclipse 3]: phrase(sentence, [hello,there],X).

no (more) solution.
</PRE></BLOCKQUOTE>
<A NAME="toc101"></A>
<H3 CLASS="subsection"><A NAME="htoc169">12.3.2</A>&nbsp;&nbsp;Mapping to Prolog Clauses</H3>
Grammar rule are translated to Prolog clauses by adding two arguments
which represent the input before and after the nonterminal which is
represented by the rule.
The effect of the transformation can be observed, e.g. by calling biprefexpand_clause/2../bips/kernel/compiler/expand_clause-2.html:
<BLOCKQUOTE CLASS="quote"> <PRE CLASS="verbatim">
[eclipse 1]: expand_clause(p(X) --&gt; q(X), Expanded).

X = X
Expanded = p(X, _250, _243) :- q(X, _250, _243)
Yes (0.00s cpu)
[eclipse 2]: expand_clause(p(X) --&gt; [a], Expanded).

X = X
Expanded = p(X, _251, _244) :- 'C'(_251, a, _244)
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
<A NAME="toc102"></A>
<H3 CLASS="subsection"><A NAME="htoc170">12.3.3</A>&nbsp;&nbsp;Parsing other Data Structures</H3>
DCGs are in principle not limited to the parsing of lists.
The predicate <A HREF="../bips/kernel/termmanip/C-3.html"><B>'C'/3</B></A><A NAME="@default689"></A> is responsible for reading resp. generating
the input tokens. The default definition is
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
'C'([Token|Rest], Token, Rest).
</PRE></BLOCKQUOTE>
The first argument represents the parsing input before consuming
Token and Rest is the input after consuming Token.<BR>
<BR>
By redefining 'C'/3, it is possible to apply a DCG to other
input sources than a list, e.g. to parse directly from an I/O stream:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
:- local 'C'/3.
'C'(Stream-Pos0, Token, Stream-Pos1) :-
        seek(Stream, Pos0),
        read_string(Stream, " ", _, TokenString),
        atom_string(Token, TokenString),
        at(Stream, Pos1).

 sentence --&gt; noun, [is], adjective.
 noun --&gt; [prolog] ; [lisp].
 adjective --&gt; [boring] ; [great].
</PRE></BLOCKQUOTE>
This can then be applied to a string as follows:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
[eclipse 1]: String = "prolog is great", open(String, string, S),
             phrase(sentence, S-0, S-End).
...
End = 15
yes.
</PRE></BLOCKQUOTE>
Here is another redefinition of 'C'/3, using a similar idea, which allows
the direct parsing of ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> strings as sequences of characters:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
:- local 'C'/3.
'C'(String-Pos0, Char, String-Pos1) :-
        Pos0 =&lt; string_length(String),
        string_code(String, Pos0, Char),
        Pos1 is Pos0+1.

anagram --&gt; [].
anagram --&gt; [_].
anagram --&gt; [C], anagram, [C].
</PRE></BLOCKQUOTE>
This can then be applied to a string as follows:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
[eclipse 1]: phrase(anagram, "abba"-1, "abba"-5).
yes.
[eclipse 2]: phrase(anagram, "abca"-1, "abca"-5).
no (more) solution.
</PRE></BLOCKQUOTE>
Unlike the default definition, these redefinitions of 'C'/3 are not bi-directional.
Consequently, the grammar rules using them can only be used for parsing,
not for generating sentences.<BR>
<BR>
Note that every grammar rule uses that definition of 'C'/3 which is visible in
the module where the grammar rule itself is defined.<BR>
<BR>
<HR>
<A HREF="umsroot068.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="umsroot066.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
</BODY>
</HTML>
